package 二零年8月;

/**
 * 圆圈中最后剩下的数字
 * 0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
 * 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
 *
 * 思路：典型的约瑟夫环问题，因为不是链表结构，所以可以用递推公式解决问题。
 *  公式： f（N,M）=(f(N-1,M)+M)%N;        此公式是利用反推法获得
 *  f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号
 * f(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号
 *
 * *理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人，其实就是把这个数组向前移动了M位。然后逆过来，就可以得到这个递推式。
 *
 *  将递归公式转为迭代
 * 递推公式的博客：https://blog.csdn.net/u011500062/article/details/72855826
 *
 */
public class S62 {
    public int lastRemaining(int n, int m) {
        int pos=0;
        for (int i = 2; i <=n ; i++) {
            pos=(pos+m)%i;
        }
        return pos;
    }
}
